package _02_链表;

public class _203_移除链表元素 {

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode newHead = removeElements(head.next, val);
        if (head.val == val) {
            head.next = newHead;
            return head;
        } else {
            return newHead;
        }
    }

    // 非递归
    public ListNode removeElements5(ListNode head, int val) {
        // 创建新头部
        ListNode newHead = new ListNode(0);
        ListNode newTail = newHead;
        while (head != null) {
            if (head.val != val) {
                newTail = newTail.next = head;
            }
            head = head.next;
        }
        newTail.next = null;
        return newHead.next;
    }

    // 非递归
    public ListNode removeElements1(ListNode head, int val) {
        // 保存链表头部的首地址
        ListNode currentHead = head;
        ListNode prevHead = null;
        while (currentHead != null) {
            if (val == currentHead.val) {
                if (prevHead == null) {
                    head = currentHead.next;
                } else {
                    prevHead.next = currentHead.next;
                }
            } else {
                // 向下衍生，到子地址
                prevHead = currentHead;
            }
            currentHead = currentHead.next;
        }
        return head;
    }

    // 递归，从后往前，因为是head.next，一个一个向下找
    public ListNode removeElements2(ListNode head, int val) {
        // 空数组
        if (head == null) return null;
        // 因为裁剪，所以需要设置
        head.next = removeElements2(head.next, val);
        return head.val == val? head.next: head;
    }

    // 递归，从后往前，因为是head.next，一个一个向下找
    public ListNode removeElements3(ListNode head, int val) {
        // 空链表
        if (head == null) return null;
        // 1.寻找递归出口，当存在
        if (head.next == null) {
            // 当前只存在一个元素
            if (head.val == val) {
                return null;
            } else {
                return head;
            }
        }
        // 2.判断函数的作用是什么，返回一个已经移除指定元素的集合
        head.next = removeElements(head.next, val);
        // 3.宏观上具体操作步骤是什么
        if (head.val == val) {
            // 移除head元素
            return head.next;
        } else {
            return head;
        }
    }
}
